/**
题目:
    请判断一个链表是否为回文链表。
    示例 1:
    输入: 1->2
    输出: false
    示例 2:
    输入: 1->2->2->1
    输出: true
    进阶：
    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路:
    找中点,反转,比较
效果:
    执行用时：12 ms, 在所有 Go 提交中击败了95.21%的用户
    内存消耗：5.5 MB, 在所有 Go 提交中击败了93.60%的用户
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    mid := getMid(head)
    p := reverse(mid.Next)
    mid.Next = nil
    q := head
    for p != nil && q != nil{
        if q.Val != p.Val{
            return false
        }
        p = p.Next
        q = q.Next
    }
    return true
}
func reverse(head *ListNode)*ListNode{
    if head == nil || head.Next == nil{
        return head
    }
    var pre *ListNode
    cur := head
    for cur != nil{
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}
func getMid(head *ListNode)*ListNode{
    if head == nil || head.Next == nil{
        return head
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}